//
// Created by DengLibin on 2019/1/14 0014.
//
#include <iostream>
#include <vector>
using namespace std;
/**
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
 */
int  binary_search(vector<int> nums,int startIndex, int endIndex, int num){
    if(num > nums[endIndex]){
        return endIndex+1;
    }
    int middleIndex = (startIndex + endIndex)/2;
    if(middleIndex == startIndex){
        return nums[middleIndex] >= num ? middleIndex : middleIndex+1;
    }
    if(nums[middleIndex] == num ){
        return middleIndex;
    }else if(nums[middleIndex] < num){
        return binary_search(nums, middleIndex, endIndex, num);
    }
    return binary_search(nums, startIndex, middleIndex,num);

}


int main63(){
    vector<int > nums;
    nums.push_back(1);
    /*nums.push_back(3);
    nums.push_back(5);
    nums.push_back(7);
    nums.push_back(9);
    nums.push_back(45);
    nums.push_back(120);
    nums.push_back(200);
    nums.push_back(201);*/
    int index = binary_search(nums, 0, nums.size() - 1, 1);
    cout <<index << ":" << nums[index];

    return 0;
}
